using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using NUnit.Framework;

namespace ProjectEuler.Core
{
    public class Problem18 : IProjectEulerProblem
    {
        protected const string triangle =
                @"75
                95 64
                17 47 82
                18 35 87 10
                20 04 82 47 65
                19 01 23 75 03 34
                88 02 77 73 07 63 67
                99 65 04 28 06 16 70 92
                41 41 26 56 83 40 80 70 33
                41 48 72 33 47 32 37 16 94 29
                53 71 44 65 25 43 91 52 97 51 14
                70 11 33 28 77 73 17 78 39 68 17 57
                91 71 52 38 17 14 91 43 58 50 27 29 48
                63 66 04 68 89 53 67 30 73 16 69 87 40 31
                04 62 98 27 23 09 70 98 73 93 38 53 60 04 23";

        protected IList<int[]> ListOfRows(string rows)
        {
            var sr = new StringReader(rows);
            var list = new List<int[]>();
            while(true)
            {
                string line = sr.ReadLine();
                if(line == null)
                {
                    return list;
                }
                list.Add(StringArrayToIntArray(line.Trim().Split(' ')));
            }
        }

        private int[] StringArrayToIntArray(string[] strarray)
        {
            var intarray = new int[strarray.Length];
            for(int i=0;i<strarray.Length;i++)
            {
                intarray[i] = int.Parse(strarray[i]);
            }
            return intarray;
        }

        protected int CalculateMaxPath(IList<int[]> rows)
        {
            for(int i=rows.Count-2;i>=0;i--)
            {
                var row = rows[i];
                var underrow = rows[i + 1];
                var calcrow = new int[row.Length];

                for(int j=0;j<row.Length;j++)
                {
                    int maxval = row[j];
                    if (underrow[j] > underrow[j + 1])
                    {
                        maxval += underrow[j];
                    }
                    else
                    {
                        maxval += underrow[j + 1];
                    }
                    calcrow[j] = maxval;
                }
                calcrow.CopyTo(rows[i], 0);
            }

            return rows[0][0];
        }

        public int Number
        {
            get { return 18; }
        }

        public string Description
        {
            get { return "Find the maximum total from top to bottom of the triangle"; }
        }

        public string Answer
        {
            get { return CalculateMaxPath(ListOfRows(triangle)).ToString(); }
        }
    }

    [TestFixture]
    public class Problem18Tests : Problem18
    {
        private string smalltriangle = @"3
                                        7 4
                                        2 4 6
                                        8 5 9 3";

        [Test]
        public void ListOfRows_returns_15_rows_on_the_given_triangle()
        {
            Assert.AreEqual(15, ListOfRows(triangle).Count);
        }

        [Test]
        public void ListOfRows_returns_4_rows_on_the_small_triangle()
        {
            Assert.AreEqual(4, ListOfRows(smalltriangle).Count);
        }

        [Test]
        public void Max_path_through_small_triangle_is_23()
        {
            Assert.AreEqual(23, CalculateMaxPath(ListOfRows(smalltriangle)));
        }
    }
}